package com.test.demo;

/**
 * Created by jl on 2017/11/28.
 * 0,1背包动态规划
 */
public class Backpack {

    // 填表法
    private static int findMax(int number, int capacity, int[] w, int[] v) {
        int[][] s = new int[number + 1][capacity + 1];
        for(int i = 1; i <= number; i++) {// i代表前i件物品的最优组合，j代表可用空间
            for (int j = 1; j <= capacity; j++) {
                if (w[i] <= j) {//能装下的情况
                    int a = s[i - 1][j - w[i]] + v[i]; //装，倒着想，先把当前的第i个物品装下得到一个价值，再加上剩余j-w[i]空间和前i-1个物品的最优解价值
                    int b = s[i - 1][j]; //不装
                    s[i][j] = a > b ? a : b;
                } else {
                    s[i][j] = s[i - 1][j];
                }
            }
        }
        return s[number][capacity];
    }

    public static void main(String[] args) {
        int number = 4;
        int capacity = 8;
        int[] w = {0, 2, 3, 4, 5};
        int[] v = {0, 3, 4, 5, 6};

        System.out.println(findMax(number, capacity, w, v));
    }

    /**
     * 优化，用一维数组存储
     */
    private static int findMaxOptimize(int number, int capacity, int[] w, int[] v) {
        int[] s = new int[capacity + 1];
        for(int i = 1; i<= number; i++) {
            for(int j=capacity; j>=0; j--) {
                if (j - w[i] >= 0 && s[j] <= s[j - w[i]] + v[i]) {
                    s[j] = s[j - w[i]] + v[i];
                }
            }
        }
        return s[capacity];
    }
}
